
import java.nio.charset.StandardCharsets;

        import java.security.MessageDigest;

        import java.security.NoSuchAlgorithmException;

        import java.util.ArrayList;

        import java.util.Arrays;

        import java.util.List;

public class Main {

    private static final String HASH_ALGORITHM = "SHA-256";



    private static byte[] hash(String input) throws NoSuchAlgorithmException {

        MessageDigest digest = MessageDigest.getInstance(HASH_ALGORITHM);

        return digest.digest(input.getBytes(StandardCharsets.UTF_8));

    }



    private static List<byte[]> buildLevel(List<byte[]> level) throws NoSuchAlgorithmException {
                            //在后面返回来的是一个集合
        //将当前层级的哈希值组合并哈希，生成下一层级的哈希值。

        List<byte[]> nextLevel = new ArrayList<>();
        //下一层


        for (int i = 0; i < level.size(); i += 2) {

            byte[] leftHash = (i < level.size()) ? level.get(i) : new byte[0];
              //  创建左节点    //如果小于总的序号就i+1
            byte[] rightHash = (i + 1 < level.size()) ? level.get(i + 1) : new byte[0];
             //创建右节点//                                                  //分配一个新的空间


            // Concatenate the hashes

            byte[] concatenated = new byte[leftHash.length + rightHash.length];
//累加左右节点        //合并以后的取名
            System.arraycopy(leftHash, 0, concatenated, 0, leftHash.length);
                   // 数组复制
            System.arraycopy(rightHash, 0, concatenated, leftHash.length, rightHash.length);
                                                                //跟着末尾进行复制


            // Hash the concatenated hashes

            byte[] combinedHash = hash(bytesToHex(concatenated));
                   //组合体的       //16进制
            nextLevel.add(combinedHash);
          //合并之后的名字
        }



        // If there's an odd number of nodes in the level, add the last node as-is

        if (level.size() % 2 != 0) {
    //是否为偶数个数，，
            nextLevel.add(level.get(level.size() - 1));
            //若不是，在其后面再补充一个元素
        }



        return nextLevel;

    }



    private static String bytesToHex(byte[] hash) {

        StringBuilder hexString = new StringBuilder();

        for (byte b : hash) {

            String hex = Integer.toHexString(0xff & b);

            if (hex.length() == 1) hexString.append('0');

            hexString.append(hex);

        }

        return hexString.toString();

    }



    public static String buildMerkleRoot(List<String> data) throws NoSuchAlgorithmException {

        //用于构建整个默克尔树并返回根哈希值。

        List<byte[]> hashes = new ArrayList<>();
                    //现在是空的
        for (String item : data) {
                //经过循环得到hash值
            hashes.add(hash(item));
         //加入集合中
        }



        while (hashes.size() > 1) {
        //再重复之前的操作  两两合并 ，当它小于一就终止，
            hashes = buildLevel(hashes);

        }



        return bytesToHex(hashes.get(0));

    }



    public static void main(String[] args) throws NoSuchAlgorithmException {

        //验证数据的完整性和真实性

        List<String> data = Arrays.asList("Data1", "Data2", "Data3", "Data4", "Data5");

        String merkleRoot = buildMerkleRoot(data);

        System.out.println("Merkle Root: " + merkleRoot);

    }

}